class Solution { 
    //解法二:使用递归(暴搜)会超时,因为存在大量完全相同的问题，所以使用记忆化搜索来做优化
public:
    int dfs(vector<int>& nums, int pos, vector<int>& memo)
    {
        //3.进入递归时,先去备忘录中查找是否已经存储了该状态的结果值
        if(memo[pos] != -1) return memo[pos]; 
        //防止pos为最后一个元素,循环进不去,符合递增子序列(长度为1)
        int ret = 1;
        //遍历pos后面所有位置,统计出所有情况下的最大值
        for(int i = pos + 1; i < nums.size(); i++)
        {
            //nums[i]可以插到pos位置后面
            if(nums[pos] < nums[i]) 
            {
                //统计以pos为起点的最长递增子序列的长度
                ret = max(ret, dfs(nums, i, memo) + 1); 
            }
        } 
        memo[pos] = ret;  //2.递归返回前,将结果值存入到备忘录中
        return ret; 
    }

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        //1.创建备忘录,只有一个可变参数,使用一维数组
        vector<int> memo(n, -1); 
        int ret = 0;
        //不知道最终最长的递增子序列是以哪个位置为起点
        for(int i = 0; i < n; i++) 
            ret = max(ret, dfs(nums, i, memo));
        return ret;
    }
};